package 强化训练;

public class day24礼物的最大价值 {

    public static void main(String[] args) {
        int[][] arr = new int[6][6];
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                arr[i][j] = 100;
            }
        }
        arr[1][4] = 200;
        System.out.println(maxValue(arr));
        System.out.println(maxValueDP(arr));
    }


    //递归
    public static int maxValue(int[][] arr){
        return maxVauleHelp(arr,0,0);
    }

    public static int maxVauleHelp(int[][] arr ,int x ,int y){
        if (x == arr.length - 1 && y == arr[0].length - 1){
            return arr[x][y];
        }

        if (x > arr.length - 1 || y > arr.length - 1){
            return 0;
        }
        int val1 = 0;
        int val2 = 0;
        if (x + 1 < arr.length){
            val1 = maxVauleHelp(arr,x + 1,y) + arr[x][y];
        }
        if (y + 1 < arr[0].length){
            val2 = maxVauleHelp(arr,x,y+1) + arr[x][y];
        }

        return Math.max(val1,val2);
    }


    //动规
    public static int maxValueDP(int[][] arr){
        for (int i = 1; i < arr[0].length; i++) {
            arr[0][i] = arr[0][i-1] + arr[0][i];
        }

        for (int i = 1; i < arr.length; i++) {
            arr[i][0] = arr[i-1][0] + arr[i][0];
        }

        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                arr[i][j] = Math.max(arr[i-1][j],arr[i][j-1]) + arr[i][j];
            }
        }

        return arr[arr.length - 1][arr[0].length - 1];
    }
}
